package com.learn.algorlthm;

import java.util.List;
import java.util.Stack;

/**
 * @author: yfpu(fengpu.yang@ucarinc.com)
 * @Date: 2018-07-06 10:40
 *
 * 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针
 *
 */
public class Learn08 {

    /**
     * 解题思路
     * https://github.com/CyC2018/Interview-Notebook/blob/master/notes/%E5%89%91%E6%8C%87%20offer%20%E9%A2%98%E8%A7%A3.md#8-%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E4%B8%8B%E4%B8%80%E4%B8%AA%E7%BB%93%E7%82%B9
     *
     */

    static class TreeLinkNode{
        public String value  = null;
        public TreeLinkNode left = null;
        public TreeLinkNode right = null;
        public TreeLinkNode parent = null;

        public TreeLinkNode(String value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return "TreeLinkNode{" +
                    "value='" + value + '\'' +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }


    public static TreeLinkNode getNext(TreeLinkNode node) {
        if (node == null)
            return null;

        if (node.right != null) {
            //右节点不为空
            TreeLinkNode temp = node.right;
            while (temp.left != null)
                temp = temp.left;
            System.out.println(temp.value);
            return temp;

        } else {
            while (node.parent != null) {
                TreeLinkNode parent = node.parent;
                if (parent.left == node) {
                    System.out.println(parent.value);
                    return parent;
                }
                node = node.parent;
            }
        }

        return null;
    }









    //region    扩展知识
    public static TreeLinkNode createTreeLinkNode() {
        String[] array = {"A", "B", "C", "D", "E", "F", "G"};
        TreeLinkNode node = new TreeLinkNode(array[0]);
        TreeLinkNode root = node;

        boolean flag = true;
        Stack<TreeLinkNode> stack = new Stack<>();

        for (int i = 0; i < array.length; i++) {
            if (i == 0)
                continue;

            if (flag) {
                node.left = new TreeLinkNode(array[i]);
                node.left.parent = node;
                stack.add(0, node.left);
            } else {
                node.right = new TreeLinkNode(array[i]);
                node.right.parent = node;
                stack.add(0, node.right);
            }
            if (node.left != null
                    && node.right != null) {
                node = stack.pop();
            }


            flag = !flag;//下次处理另一个节点
        }

        return root;
    }

    public static void inIterator(TreeLinkNode node) {
        if (node == null)
            return;
        inIterator(node.left);
        System.out.println(node.value);
        inIterator(node.right);
    }


    //endregion


}
